package lineartable.linkedlist.circularlinkedlist;

import lineartable.inter.LinearLinkedList;

/**
 * 线性表的链式存储结构-循环链表
 */
public class CircularLinkedList implements LinearLinkedList {
    // 指向尾节点的引用
    private CircularLinkedNode rear;

    public CircularLinkedList() {
        rear = new CircularLinkedNode();
        // 尾节点指向头节点，链表中没有元素时，尾节点引用的next指向头节点
        rear.setNext(rear);
    }

    /**
     * 头插法建表
     *
     * @param data
     */
    @Override
    public void createListHead(char data) {
        CircularLinkedNode head = rear.getNext();
        CircularLinkedNode temp = new CircularLinkedNode();
        temp.setData(data);
        temp.setNext(head.getNext());
        head.setNext(temp);
        // 判断插入的元素是否是该列表中的第一个插入的元素，如果是，则改变rear引用指向的该元素
        // 这种写法比较勉强，但暂时没有想到什么办法。。。。。。
        if (head.getNext().getNext() == head) {
            rear = temp;
        }
    }

    /**
     * 尾插法建表
     *
     * @param data
     */
    @Override
    public void createListTail(char data) {
        CircularLinkedNode temp = new CircularLinkedNode();
        temp.setData(data);
        temp.setNext(rear.getNext());
        rear.setNext(temp);
        rear = temp;
    }

    /**
     * 返回线性表是否为空
     *
     * @return
     */
    @Override
    public boolean listEmpty() {
        return rear.getNext() == rear;
    }

    /**
     * 将线性表清空
     */
    @Override
    public void clearList() {
        rear = rear.getNext();
        rear.setNext(rear);
    }

    /**
     * 返回线性表中第i个位置元素
     *
     * @param index
     * @return
     */
    @Override
    public char getElem(int index) {
        CircularLinkedNode p = rear.getNext();
        for (int i = 0; i <= index; i++) {
            p = p.getNext();
        }
        return p.getData();
    }

    /**
     * 查找线性表中的元素，并返回下标
     *
     * @param e
     * @return
     */
    @Override
    public int locateElem(char e) {
        CircularLinkedNode p = rear.getNext();
        int i = 0;
        while ((p = p.getNext()) != rear.getNext()) {
            if (p.getData() == e) {
                return i;
            }
            i++;
        }
        return -1;
    }

    /**
     * 在线性表第i个位置插入元素e
     *
     * @param i
     * @param e
     */
    @Override
    public void listInsert(int i, char e) {
        if (i < 0 || i > getListLength()) {
            return;
        }
        CircularLinkedNode p = rear.getNext();
        for (int j = 0; j < i; j++) {
            p = p.getNext();
        }
        CircularLinkedNode temp = new CircularLinkedNode();
        temp.setData(e);
        temp.setNext(p.getNext());
        p.setNext(temp);
    }

    /**
     * 删除链表中的第i个元素
     *
     * @param i
     */
    @Override
    public void listDelete(int i) {
        CircularLinkedNode p = rear.getNext();
        for (int j = 0; j < i; j++) {
            p = p.getNext();
        }
        p.setNext(p.getNext().getNext());
    }

    /**
     * 返回线性表中元素个数
     *
     * @return
     */
    @Override
    public int getListLength() {
        int i = 0;
        CircularLinkedNode p = rear.getNext();
        while (p.getNext() != rear.getNext()) {
            p = p.getNext();
            i++;
        }
        return i;
    }

    /**
     * 把另一个循环链表中的元素添加到当前循环链表中
     *
     * @param cirList
     */
    public void addList(CircularLinkedList cirList) {
        CircularLinkedNode head = rear.getNext();
        rear.setNext(cirList.rear.getNext().getNext());
        cirList.rear.setNext(head);
        rear = cirList.rear;
    }

    /**
     * 合并两个循环链表
     *
     * @param listA 第一个循环链表
     * @param listB 第二个循环链表
     * @return
     */
    public static CircularLinkedList margeList(CircularLinkedList listA, CircularLinkedList listB) {
        CircularLinkedNode rearB = listB.rear;
        CircularLinkedNode headA = listA.rear.getNext();
        listA.rear.setNext(rearB.getNext().getNext());
        rearB.setNext(headA);
        listA.rear = rearB;
        return listA;
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");

        CircularLinkedNode p = rear.getNext();
        while ((p = p.getNext()) != rear.getNext()) {
            stringBuilder.append(p.getData() + ",");
        }

        // 如果数组中有元素才删除最后一个“，”符号
        if (stringBuilder.length() > 1) {
            stringBuilder.deleteCharAt(stringBuilder.length() - 1);
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }
}
